package com.xyhuo.leetcode;

public class CountPrimes {

    public int countPrimes(int n) {
        int[] list = new int[n];
        for (int i = 2; i <= n / 2; i++) {
            if (Math.pow(i, 2) > n) {
                break;
            }
            for (int j = i; j <= n / 2; j++) {
                if (i * j < n) {
                    list[i * j - 1] = 1;
                } else {
                    break;
                }
            }
        }

        int result = 0;
        for (int i = 1; i < n - 1; i++) {
            if (list[i] == 0) {
                result++;
            }
        }
        return result;

    }

    public static void main(String[] args) {
        CountPrimes c = new CountPrimes();
        int i = c.countPrimes(499979);
        System.out.println(i);

    }
}
